package com.zwh.algorithm.leetcode.medium;

import java.util.Arrays;

public class LeetCode2679 {
    /**
     * 2023-07-04 矩阵中的和
     * todo 给你一个下标从 0 开始的二维整数数组 nums 。一开始你的分数为 0 。你需要执行以下操作直到矩阵变为空：
     * todo 1.矩阵中每一行选取最大的一个数，并删除它。如果一行中有多个最大的数，选择任意一个并删除。
     * todo 2.在步骤 1 删除的所有数字中找到最大的一个数字，将它添加到你的 分数中。
     * todo 请你返回最后的分数。
     * todo 输入：nums = [[7,2,1],[6,4,2],[6,5,3],[3,2,1]]
     * todo 输出：15
     * todo 解释：第一步操作中，我们删除 7 ，6 ，6 和 3 ，将分数增加 7 。下一步操作中，删除 2 ，4 ，5 和 2 ，将分数增加 5 。最后删除 1 ，2 ，3 和 1 ，将分数增加 3 。所以总得分为 7 + 5 + 3 = 15 。
     * @param args
     */
    public static void main(String[] args) {
        int[][] nums = {{7,2,1},{6,4,2},{6,5,3},{3,2,1}};
        int[][] nums1 = {{1,8,16,15,12,9,15,11,18,6,16,4,9,4},
                {3,19,8,17,19,4,9,3,2,10,15,17,3,11},
                {13,10,19,20,6,17,15,14,16,8,1,17,0,2},
        {12,20,0,19,15,10,7,10,2,6,18,7,7,4},
        {17,14,2,2,10,16,15,3,9,17,9,3,17,10},
        {17,6,19,17,18,9,14,2,19,12,10,18,7,9},
        {5,6,5,1,19,8,15,2,2,4,4,1,2,17},
        {12,16,8,16,7,6,18,13,18,8,14,15,20,11},
        {2,10,19,3,15,18,20,10,6,7,0,8,3,7},
        {11,5,10,13,1,3,4,7,1,18,20,17,19,2},
        {0,3,20,6,19,18,3,12,2,11,3,1,19,0},
        {6,5,3,15,6,1,0,17,13,19,3,8,2,7},
        {2,20,9,11,13,5,1,16,14,1,19,3,12,6}};
        System.out.println(matrixSum(nums));
        System.out.println(matrixSum(nums1));
    }
    /**思路：排序
     * 由于每次删除操作中，每行删除的元素即为当前行中的最大值，
     * 因此我们可以直接将每行的元素按照从大到小排序，然后按照列遍历矩阵，
     * 每次删除操作得分即为当前列的最大值，因此最终得分即为所有列中的最大值之和。
     */
    public static int matrixSum(int[][] nums) {
        int sum = 0;
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            Arrays.sort(nums[i]);
        }
        for (int i = 0; i < nums[0].length ; i++) {
            int max = 0;
            for (int j = 0; j < length ; j++) {
                int a = nums[j][i];
                if (max<a){
                    max = a;
                }
            }
            sum+=max;
        }
        return sum;
    }

}
